package com.problem.leetcode;

/**
 * @author didi
 * @DESCRIPTION
 * @create 2019-04-28 18:16
 **/

public class Problem204 {
    public int countPrimes(int n) {
        int count = 0;
        for (int index = 2; index < n; index++) {
            if (isPrime2(index)) {
                ++count;
            }
        }
        return count;
    }

    private boolean isPrime(int num) {
        int step = 2;
        while (step * step <= num) {
            if (num % step == 0) {
                return false;
            }
            step += 1;
        }
        return true;
    }

    private boolean isPrime2(int num) {
        if (num == 2 || num == 3) {
            return true;
        }
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }

        if (num <= 36) {
            return isPrime(num);
        }

        int tmp = 6;
        while (((tmp - 1) * (tmp - 1)) <= num) {
            if (num % (tmp - 1) == 0 || num % (tmp + 1) == 0) {
                return false;
            }
            tmp += 6;
        }
        return true;
    }

}
